package niuke.week02;

import java.util.Scanner;

/**
 * 二叉树中一个节点的后继节点指的是，二叉树的中序遍历的序列中的下一个节点。
 */
public class PostNodeOfTree {
    static Scanner sc = new Scanner(System.in);
    static class Node {
        Node leftNode;
        Node rightNode;
        Node parent;
        int value;

        public Node(int value) {
            this.value = value;
        }

    }

    public static void main(String[] args) {
        int n = sc.nextInt();//节点个数
        int rootValue = sc.nextInt();//根节点

        Node head = buildTree(null);

        int target = sc.nextInt();

//        inOrder(head);
        Node curNode = getNode(head, target);//在树中找到这个节点

        if(curNode.rightNode!=null){//存在右子树，下一个节点为右子树的最左节点
            Node node = curNode.rightNode;
            while (node.leftNode!=null)//找到最左子节点
                node = node.leftNode;

            System.out.println(node.value);
        }else {
            if(isLeft(curNode)){//如果他是左子节点,下一个为父节点
                System.out.println(curNode.parent.value);
            }else {//如果他是右子节点，下一个为左父节点的父节点
                Node node = curNode.parent;
                while (node!=null && !isLeft(node))
                    node = node.parent;

                if(node!=null)
                     System.out.println(node.parent.value);
                else
                    System.out.println(0);
            }
        }
    }

    public static Node getNode(Node node,int val){
        if(node==null)
            return null;

        Node left = getNode(node.leftNode, val);
        Node right = getNode(node.rightNode, val);

        if(node.value == val)
            return node;
        else
            return  left!= null ?left:right;
    }

    public static void inOrder(Node node){
        if(node==null)
            return;
        inOrder(node.leftNode);
        System.out.print(node.value+" ");
        inOrder(node.rightNode);
    }

    public  static Node buildTree(Node parent){
        int value = sc.nextInt();
        int leftValue = sc.nextInt();
        int rightValue = sc.nextInt();

        Node node = new Node(value);
        node.parent = parent;


        if(leftValue!=0){
            Node node1 = buildTree(node);
            node.leftNode =node1;
//            System.out.println(node.value+"的左子树"+node1.value);
        }
        if(rightValue!=0){
            Node node2= buildTree(node);
            node.rightNode = node2;
//            System.out.println(node.value+"的右子树"+node2.value);
        }

        return  node;
    }

    public  static  boolean isLeft(Node node){
        if (node==null)
            return false;

        if(node.parent==null)
            return false;

        return  node.parent.leftNode==node;
    }

}